#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &cands, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		vector<vector<int> > result;
		if(cands.empty())
			return result;

		sort(cands.begin(),cands.end());

		vector<int> counts(cands.size(),0);

		solve(cands, result, 0, 0, target, counts);

		return result;
    }

private:
	void solve(const vector<int>& cands, vector<vector<int> >& result,int sum, size_t index, int target,vector<int>& counts){
		if(sum > target)
			return;
		

		if(sum == target){
			vector<int> r;
			for(int i=0;i<index;i++){
				if(counts[i] > 0){
					for(int j=0;j<counts[i];j++){
						r.push_back(cands[i]);
					}
				}
			}
			result.push_back(r);
			return;
		}

		if(index >= cands.size())
			return;

		int left = target - sum;
		for(int i=0;left>=0;left-=cands[index],sum+= cands[index],i++){
			counts[index] = i;
			solve(cands,result,sum,index+1,target,counts);
		}
	}
};
#endif